package com.cat.dynamicPlanning02;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/flip-string-to-monotone-increasing/?envType=problem-list-v2&envId=dynamic-programming
 * @create 2025/10/1 21:33
 * @since JDK17
 */

public class Solution14 {
    public int minFlipsMonoIncr(String s) {
        char[] arr = s.toCharArray();
        int n = arr.length;
        int[][] dp = new int[n][2];
        dp[0][0] = arr[0] == '0' ? 0 : 1;
        dp[0][1] = arr[0] == '0' ? 1 : 0;
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][0] + (arr[i] == '0' ? 0 : 1);
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + (arr[i] == '0' ? 1 : 0);
        }
        return Math.min(dp[n - 1][0], dp[n - 1][1]);
    }
}
